import java.util.Arrays;

/**
 * 977. 有序数组的平方
 * https://leetcode-cn.com/problems/squares-of-a-sorted-array/
 */
public class Solutions_977 {
    public static void main(String[] args) {
//        int[] nums = {-4, -1, 0, 3, 10};  // output: {0, 1, 9, 16, 100}
        int[] nums = {-7, -3, 2, 3, 11};  // output: {4, 9, 9, 49, 121}

        int[] result = sortedSquares(nums);
        System.out.println(Arrays.toString(result));
    }

    public static int[] sortedSquares(int[] A) {
        int len = A.length;
        int[] res = new int[len];
        // res 数组中，从后往前放
        int idx = len - 1;
        int left = 0, right = len - 1;
        while (left <= right) {
            if (Math.abs(A[left]) > Math.abs(A[right])) {
                // 先放大的
                res[idx] = A[left] * A[left];
                left ++;
            } else {
                res[idx] = A[right] * A[right];
                right --;
            }
            idx --;
        }
        return res;
    }
}
